package com.cty._04_Optimization._50_02_FirstNotRepeatingCharInStream;

/**
 * @Auther: cty
 * @Date: 2020/7/20 9:48
 * @Description: 面试题50（二）：字符流中第一个只出现一次的字符
 * 题目：请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从
 * 字符流中只读出前两个字符"go"时，第一个只出现一次的字符是'g'。当从该字
 * 符流中读出前六个字符"google"时，第一个只出现一次的字符是'l'。
 * @version: 1.0
 */
public class FirstNotRepeatingCharInStream {
    /**
     * n：该字符在流中的顺序
     * 0：该字符未出现过
     * -1：该字符至少出现两次
     */
    private int[] occurrence;
    private int index;

    public FirstNotRepeatingCharInStream(){
        occurrence = new int[256];
        index = 1;
    }

    public void insert(char c) throws Exception {
        if(occurrence[c] > 0)
            occurrence[c] = -1;
        else if(occurrence[c] == 0)
            occurrence[c] = index;

        if(++index > Integer.MAX_VALUE)
            throw new Exception("接收的字符流超过最大限制！");
    }  // end insert()

    public char getFirstAppearingOnce(){
        if(index == 0)
            return '$';

        // 找到索引值最小的只出现一次的字符
        int minIndex = occurrence.length;
        char ch = '$';
        for(int i=0; i<occurrence.length; i++)
            if(occurrence[i]>0 && occurrence[i]<minIndex){
                minIndex = occurrence[i];
                ch = (char)i;
            }
        return ch;
    }  // end getFirstAppearingOnce

}  // end class
